package main

import "fmt"

func main() {
	fmt.Println(numDecodings("0342425"))
}

func numDecodings(s string) int {
	if s == "" || s[0] == '0' {
		return 0
	}
	dp := make([]int, len(s)+1)
	dp[0] = 1
	dp[1] = 1
	for k := 1; k < len(s); k++ {
		if s[k] == '0' && s[k-1] != '1' && s[k-1] != '2' {
			return 0
		} else if s[k] == '0' && (s[k-1] == '1' || s[k-1] == '2') {
			dp[k+1] = dp[k+1-2]
		} else if s[k-1] == '0' || (s[k-1] == '2' && s[k] >= '7' && s[k] <= '9') || (s[k-1] >= '3' && s[k-1] <= '9' && s[k] != '0') {
			dp[k+1] = dp[k+1-1]
		} else {
			dp[k+1] = dp[k+1-1] + dp[k+1-2]
		}
	}
	return dp[len(dp)-1]
}
